20. Valid Parentheses

Question

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

Open brackets must be closed by the same type of brackets. Open brackets must be closed in the correct order.

Example 1:

Input: s = "()"
Output: true

Example 2:

Input: s = "()[]{}"
Output: true

Example 3:

Input: s = "(]"
Output: false

Constraints:

1 <= s.length <= 104
s consists of parentheses only '()[]{}'.

---

Approach

1. If there is only a single paranthesis in the input, it is false for sure.
2. Check the input for open / close parenthesis i.e. '(', '{', '['
3. If any of these 3 are found, add the corresponding closing parenthesis to the stack.
4. When we found any none-opening paranthesis, check if it is indeed the one on top of the stack. If yes, pop it from the stack.
5. There is a case when we found a close paranthesis before any opening paranthesis, hence it is false too.
6. After interating the whole string, by right the stack should be empty by now. If it is not, some parenthesis was not closed, hence false.

Solution

class Solution {
public:
    bool isValid(string s) {
        if(s.size() == 1) return false;
        stack<char> par;
        
        for(int i = 0; i < s.size(); i++){
            if(s[i] == '('){ 
                par.push(')');
            }else if(s[i] == '['){
                par.push(']');
            }else if( s[i] == '{'){
                par.push('}');
            }else{
                if(par.empty()) return false;
                if(s[i] == par.top()){
                    par.pop();
                    continue;
                }
                return false;
            }
        }
        
        if(!par.empty()) return false;
        return true;
    }
};